package com.str.BT;
//  Balancing a Strict Binary Search Tree
//		using DSW Balancing Algorithm
//
public class BSTBalancing {
	
// Inner class
  private static class BSTNode {
    Comparable data;
    BSTNode left;
    BSTNode right;

    BSTNode() {}
    BSTNode(Comparable obj) { data = obj; }
    BSTNode(Comparable obj, BSTNode leftChild, BSTNode rightChild) {
      data = obj; 
      left = leftChild; 
      right = rightChild;
    }

    public String toString()
    { return data.toString(); }
  }
  
  private BSTNode root;
  private int count;
    	  	
  public void BSTBalancing() {
    root = null;
    count = 0;
  }
  
  public void insert(Comparable val) 
  { root = insert(root, val); }
  
  private BSTNode insert(BSTNode ref, Comparable val) {
  // Insert the element elem in this BST.
    if (ref == null) {
      count++;
      return new BSTNode(val);
    }
    else {
      int comp = val.compareTo(ref.data);
      if (comp < 0)
        ref.left = insert(ref.left, val);
      else  // comp >= 0
        ref.right = insert(ref.right, val);
      return ref;  	   	
    }
  }

  public String toString()  
  { return toString(root, 0); }
  
  private String toString(BSTNode ref, int level) {
  	String buf = "";
    if (ref != null) {
      buf += toString(ref.right, level+1);
      for (int i=0; i<level; i++)
        buf += "    ";
      buf += ref.data + "\n";
      buf += toString(ref.left, level+1);
    }
    return buf;
  }
	
  public void createBackbone()
  { root = createBackbone(root); } 
  
  private BSTNode createBackbone(BSTNode root) {
    if (root != null) {
   	  root.right = createBackbone(root.right);
   	  if (root.left != null) {
   	  	BSTNode oldRoot = root;
   	    BSTNode ref = root = createBackbone(root.left);  	
  	    oldRoot.left = null;    	  	  
  	    while (ref.right != null)
  	      ref = ref.right;
  	    ref.right = oldRoot;
  	  }
  	}
  	return root;
  } 	

  public void createTree()
  { root = createTree(root, count); } 
  
  private BSTNode createTree(BSTNode root, int n) {
    if (n > 2) {
      int m = (n - 1) / 2;
      BSTNode oldRoot = root;
      BSTNode ref = root; 
      for (int i=1; i<m; i++)
        ref = ref.right;
      root = ref.right;    	
      ref.right = null;
      root.left = createTree(oldRoot, m);
      root.right = createTree(root.right, n - m - 1);
    }
    return root;   	 	
  }

  public static void main(String[] args) {
  	BSTBalancing bst = new BSTBalancing();
  	
    for (int i = 0; i < 10; i++) {
      int r = (int) (Math.random() * 26);	
      bst.insert(new Character((char) ('A' + r)));	
    }
    
    System.out.print(bst);
    System.out.println("-----------------------------");
    
    bst.createBackbone();
    System.out.print(bst);
    System.out.println("-----------------------------");
    
    bst.createTree();
    System.out.print(bst);
  }
}

 
